package com.code.leetcode.offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/8/2 11:37
 */
public class The39_摩尔投票法 {
    /**
     * 最常规的方法， 26%
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        int sum = 0;
        int rtn = -1;
        for(int num : nums) {
            Integer temp = ((int)map.getOrDefault(num, 0)) + 1;
            map.put(num, temp);
            if (temp >= sum) {
                sum = temp;
                rtn = num;
            }
        }
        return rtn;
    }

    /**
     * 排序后取中间值 76%
     * @param nums
     * @return
     */
    public int majorityElementSort(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 摩尔投票法，先选取一个为初始候选者的值，如果后面的值与他相等，则票数加一
     * 如果不同则票数减一，如果票数为零的话，下一个遍历的值作为新的候选者
     * 最后剩下的一定是众数
     * 99%
     * @param nums
     * @return
     */
    public int majorityElementMoEr(int[] nums) {
        int sum = 0;
        int temp = -1;
        for (int num : nums) {
            if (sum == 0) temp = num;
            /**
             * 这个效率为74.4%
             */
            sum += temp == num ? 1 : -1;
            /**
             * 这个效率为 99%
             * if (temp == num) sum++;
             * else sum--;
             */
        }
        return temp;
    }
}
